class Solution {
public:
    int totalNQueens(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<bool> left(n * 2 - 1);
        vector<bool> right(n * 2 - 1);
        vector<int> perm(n);
        for (int i = 0; i < n; ++i) {
            perm[i] = i;
        }
        int result = 0;

        Recursive(n, 0, perm, left, right, result);
        return result;
    }

    void Recursive(int n, int depth, vector<int>& perm,
        vector<bool>& left,
        vector<bool>& right,
        int& result) {
        if (depth ==  n) {
            ++result;
            return;
        }
        for (int i = depth; i < n; ++i) {
            swap(perm[depth], perm[i]);
            if (left[depth + perm[depth]] ||
                right[depth - perm[depth] + n - 1]
            ) {
                swap(perm[depth], perm[i]);
                continue;
            }
            left[depth + perm[depth]] = true;
            right[depth - perm[depth] + n - 1] = true;
            Recursive(n, depth + 1, perm, left, right, result);

            right[depth - perm[depth] + n - 1] = false;
            left[depth + perm[depth]] = false;
            swap(perm[depth], perm[i]);
        }
    }
};